/**
 * Copyright (C) 2008+ Spark Zheng
 *
 * @file	include/list.h
 * @brief 
 *      List module, A basic datastruct module,
 *      refer to Linux kernel implementation.
 *      Memory-free operations, generic frame of list datastructs
 *      -1. list(queue)
 *      -2. hlist(stack)
 *
 * @module      dlib
 * @see		dlib
 *
 * @history
 *      version 0.1.0, spark init tree module with rbtree 
 */

#ifndef _DLIB_LIST_H
#define _DLIB_LIST_H

#ifdef __cplusplus
extern "C" {
#endif

#include "global.h"

#define LIST_POISON	NULL

/**
 * Simple double circle link list implementation,
 * and all other data-structures are based on it.
 * queue, dequeue, vector, list
 */
typedef struct list_node list_node_t;
typedef struct list_node list_head_t;
struct list_node {
	struct list_node *next;
	struct list_node *prev;
};

#define LIST_HEAD_INIT(head)	do { \
	(head)->next = (head); \
	(head)->prev = (head); } while (0)

#define LIST_FIRST(head)	((head)->next)
#define LIST_LAST(head)		((head)->prev)
#define LIST_NEXT(node) 	((node)->next)
#define LIST_PREV(node)		((node)->prev)
#define LIST_IS_FIRST(head, node) \
	((node)->prev == (head))
#define LIST_IS_LAST(head, node) \
	((node)->next == (head))

#define LIST_EMPTY(head) \
	((head)->next == (head) || (head)->prev == (head))
#define LIST_EMPTY_CAREFULLY(head) \
	((head)->next == (head) && (head)->prev  == (head))

#define LIST_ENTRY(ptr, type, member)	container_of(ptr, type, member)
#define LIST_FIRST_ENTRY(head, type, member) \
	(((head)->next == (head)) ? NULL : container_of((head)->next, type, member))
#define LIST_LAST_ENTRY(head, type, member) \
	(((head)->prev == (head)) ? NULL : container_of((head)->prev, type, member))
#define LIST_NEXT_ENTRY(head, node, type, member) \
	(((node)->next == (head)) ? NULL : container_of((node)->next, type, member))
#define LIST_PREV_ENTRY(head, node, type, member) \
	(((node)->prev == (head)) ? NULL : container_of((node)->prev, type, member))

#define LIST_ADD_HEAD(head, new)	do { \
	list_node_t *__temp = (head)->next; \
	(new)->prev = (head); \
	(head)->next = (new); \
	(new)->next = __temp; \
	__temp->prev = (new); } while(0)
#define LIST_ADD_TAIL(head, new)	do { \
	list_node_t *__temp = (head)->prev; \
	(new)->next = (head); \
	(head)->prev = (new); \
	(new)->prev = __temp; \
	__temp->next = (new); } while(0)

#define LIST_INSERT_AFTER(node, new)	do { \
	list_node_t *__temp = (node)->next; \
	(new)->prev = (node); \
	(node)->next = (new); \
	(new)->next = __temp; \
	__temp->prev = (new); } while(0)
#define LIST_INSERT_BEFORE(node, new)	do { \
	list_node_t *__temp = (node)->prev; \
	(new)->next = (node); \
	(node)->prev = (new); \
	(new)->prev = __temp; \
	__temp->next = (new); } while(0)

#define LIST_DEL(node)			do { \
	(node)->next->prev = (node)->prev; \
	(node)->prev->next = (node)->next; \
	(node)->prev = LIST_POISON; \
	(node)->next = LIST_POISON; } while(0)
#define LIST_DEL_INIT(node)		do { \
	(node)->next->prev = (node)->prev; \
	(node)->prev->next = (node)->next; \
	LIST_HEAD_INIT(node); } while(0)

#define LIST_DEL_HEAD(head, node)       do { \
	if (LIST_EMPTY(head)) { node = LIST_POISON; } \
	else { node = (head)->next; LIST_DEL(node); } } while(0)
#define LIST_DEL_TAIL(head, node)       do { \
	if (LIST_EMPTY(head)) { node = LIST_POISON; } \
	else { node = (head)->prev; LIST_DEL(node); } } while(0)

#define LIST_PUSH(head, new)		LIST_ADD_HEAD(head, new)
#define LIST_POP(head, node)		LIST_DEL_HEAD(head, node)
#define LIST_POP_ENTRY(entry, head, member)	do { \
	entry = LIST_FIRST_ENTRY((head), typeof(*(entry)), member); \
	if (entry != NULL) LIST_DEL(&(entry)->member); } while (0)

#define LIST_REPLACE(old, new)		do { \
	(new)->next = (old)->next; \
	(new)->prev = (old)->prev; \
	(old)->prev->next = (new); \
	(old)->next->prev = (new); \
	(old)->next = LIST_POISON; \
	(old)->prev = LIST_POISON; } while(0)
#define LIST_REPLACE_INIT(old, new) do { \
	(new)->next = (old)->next; \
	(new)->prev = (old)->prev; \
	(old)->prev->next = (new); \
	(old)->next->prev = (new); \
	LIST_HEAD_INIT(old); } while(0)

#define LIST_SPLICE(list, head)		do { \
	list_node_t *__temp1 = (head)->next; \
	list_node_t *__temp2 = (list)->prev; \
	(list)->prev = (head); \
	(head)->next = (list); \
	__temp1->prev = __temp2; \
	__temp2->next = __temp1; } while(0)
#define LIST_SPLICE_TAIL(list, head)	do { \
	list_node_t *__temp1 = (head)->prev; \
	list_node_t *__temp2 = (list)->prev; \
	__temp2->next = (head); \
	(head)->prev = __temp2; \
	__temp1->next = (list); \
	(list)->prev = __temp1;	} while(0)

/** 
 * These assume you really know what pos is,
 * or you should try LIST_FOREACH_ENTRY,
 * loop from list begin to list end.
 */
#define LIST_FOREACH(pos, head) \
	for (pos = (head)->next; pos != (head); pos = (pos)->next)
#define LIST_FOREACH_PREV(pos, head) \
	for (pos = (head)->prev; pos != (head); pos = (pos)->prev)
#define LIST_FOREACH_SAFE(pos, n, head) \
	for (pos = (head)->next, n = (pos)->next; pos != (head); \
		pos = n, n = (pos)->next)
#define LIST_FOREACH_PREV_SAFE(pos, n, head) \
	for (pos = (head)->prev, n = (pos)->prev; pos != (head); \
		pos = n, n = (pos)->prev)

#define LIST_FOREACH_ENTRY(tpos, pos, head, member) \
	for (pos = (head)->next; \
		pos != (head) && ({tpos = LIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
		pos = (pos)->next)
#define LIST_FOREACH_ENTRY_PREV(tpos, pos, head, member) \
	for (pos = (head)->prev; \
		pos != (head) && ({tpos = LIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
		pos = (pos)->prev)
#define LIST_FOREACH_ENTRY_SAFE(tpos, pos, n, head, member) \
	for (pos = (head)->next; \
		(pos != (head)) && ({n = (pos)->next; 1;}) && ({ \
		tpos = LIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
		pos = n)
#define LIST_FOREACH_ENTRY_PREV_SAFE(tpos, pos, n, head, member) \
	for (pos = (head)->prev; \
		(pos != (head)) && ({n = (pos)->prev; 1;}) && ({ \
		tpos = LIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
		pos = n)

/** Loop from middle list to list end which fits your meets */
#define LIST_PREPARE_ENTRY(pos, head, member) \
	(((pos) == (head)) ? NULL : LIST_ENTRY((head), typeof(*(pos)), member))
#define LIST_FOREACH_ENTRY_CONTINUE(tpos, pos, head, member) \
	for (pos = (pos)->next; pos != (head) && ({ \
		tpos = LIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
		pos = pos->next)
#define LIST_FOREACH_ENTRY_PREV_CONTINUE(tpos, pos, head, member) \
	for (pos = (pos)->prev; pos != (head) && ({ \
		tpos = LIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
		pos = pos->prev)

#define LIST_FOREACH_ENTRY_FROM(tpos, pos, head, member) \
	for (; pos != (head) && ({ \
		tpos = LIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
		pos = pos->next)
#define LIST_FOREACH_ENTRY_SAFE_FROM(tpos, pos, n, head, member) \
	for (; (pos != (head)) && ({n = (pos)->next; 1;}) && ({ \
		tpos = LIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
		pos = n)
#define LIST_FOREACH_ENTRY_PREV_FROM(tpos, pos, head, member) \
	for (; pos != (head) && ({ \
		tpos = LIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
		pos = pos->prev)
#define LIST_FOREACH_ENTRY_PREV_SAFE_FROM(tpos, pos, n, head, member) \
	for (; (pos != (head)) && ({n = (pos)->prev; 1;}) && ({ \
		tpos = LIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
		pos = n)

/**
 * Double linked lists with a single pointer list head.
 * Mostly used in hash tables where the two pointer list head is too wasteful.
 * You lose the ability to access the tail in O(1), but delete node in O(1).
 * stack may used in this way
 */
#define HLIST_POISON	NULL

typedef struct hlist_head hlist_head_t;
typedef struct hlist_node hlist_node_t;

struct hlist_node {
	struct hlist_node *next;	/** next element */
	struct hlist_node **pprev;	/** addr of previous next element */
};
struct hlist_head {
	struct hlist_node *first;	/** the list hook of hash buckets */
};

#define HLIST_HEAD_INIT(head)	((head)->first = NULL)
#define HLIST_NODE_INIT(node)	({(node)->next = NULL; (node)->pprev = NULL;})

#define HLIST_UNHASHED(node)	((node)->pprev == NULL)
#define HLIST_EMPTY(head)	((head)->first == NULL)

#define HLIST_FIRST(head)	((head)->first)
#define HLIST_NEXT(node)	((node)->next)

#define HLIST_ENTRY(node, type, member) \
	(((node) == NULL) ? NULL: container_of(node, type, member))
#define HLIST_FIRST_ENTRY(head, type, member) \
	(((head)->first == NULL) ? NULL : container_of((head)->first, type, member))

#define HLIST_NEXT_ENTRY(pos, type, member) \
	(HLIST_ENTRY((pos)->next, type, member))

#define HLIST_ADD(head, new)		do { \
	hlist_node_t *__temp = (head)->first; \
	(head)->first = new; \
	(new)->pprev = &(head)->first; \
	(new)->next = __temp; \
	if (__temp != NULL) __temp->pprev = &(new)->next; } while(0)
#define HLIST_INSERT_BEFORE(node, new)	do { \
	(new)->pprev = (node)->pprev; \
	(new)->next = (node); \
	(node)->pprev = &(new)->next; \
	*((new)->pprev) = (new); } while(0)
#define HLIST_INSERT_AFTER(node, new)	do { \
	(new)->next = (node)->next; \
	(node)->next = (new); \
	(new)->pprev = &(node)->next; \
	if ((new)->next != NULL) (new)->next->pprev = &(new)->next; } while(0)

#define HLIST_DEL(node)			do { \
	*((node)->pprev) = (node)->next; \
	if ((node)->next != NULL) (node)->next->pprev = (node)->pprev; \
	(node)->next = HLIST_POISON; \
	(node)->pprev = HLIST_POISON; } while(0)

#define HLIST_REPLACE(old, new)		do { \
	(new)->next = (old)->next; \
	(new)->pprev = (old)->pprev; \
	*((old)->pprev) = (new); \
	(old)->next = HLIST_POISON; \
	(old)->pprev = HLIST_POISON; } while(0)

#define HLIST_PUSH(head, new)		HLIST_ADD(head, new)
#define HLIST_POP(head, node)		do { \
	node = (head)->first; \
	if (node != NULL) HLIST_DEL(node); } while(0)
/** entry->member should not be a pointer */
#define HLIST_POP_ENTRY(head, member, entry)	do { \
	entry = HLIST_FIRST_ENTRY((head), typeof(*(entry)), member); \
	if ((entry) != NULL) HLIST_DEL(&(entry)->member); } while (0)

#define HLIST_FOREACH(pos, head) \
	for (pos = (head)->first; pos; pos = pos->next)
#define HLIST_FOREACH_SAFE(pos, n, head) \
	for (pos = (head)->first; pos && ({n = pos->next; 1;}); pos = n)

/** foreach entry macros requir your cautions about outputs */
#define HLIST_FOREACH_ENTRY(tpos, pos, head, member) \
	for (pos = (head)->first; \
		pos && ({tpos = HLIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
		pos = (pos)->next)
#define HLIST_FOREACH_ENTRY_SAFE(tpos, pos, n, head, member) \
	for (pos = (head)->first; \
		pos && ({n = (pos)->next; 1;}) && ({ \
		tpos = HLIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
		pos = n)

#define HLIST_FOREACH_ENTRY_CONTINUE(tpos, pos, member) \
	for (pos = (pos)->next; pos && ({ \
		tpos = HLIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
		pos = (pos)->next)
#define HLIST_FOREACH_ENTRY_FROM(tpos, pos, member) \
	for (; (pos) && ({ \
	     tpos = HLIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
	     pos = (pos)->next)
#define HLIST_FOREACH_ENTRY_SAFE_FROM(tpos, pos, n, member) \
	for (; (pos) && ({n = (pos)->next; 1;}) && ({ \
	     tpos = HLIST_ENTRY(pos, typeof(*(tpos)), member); 1;}); \
	     pos = n)

#ifdef __cplusplus
}
#endif
#endif
